package puzzle.projecteuler.p200;

import astudy.util.AdvMath;

public class Problem131C {

	/**
	 * p must like 3s^2 + 3s + 1
	 * @param args
	 */
	public static void main(String[] args) {

		int c = 0;
		Integer[] ps = AdvMath.primes(1000000);
		for (Integer p: ps) {
			if (p%3 == 1) {
				int x = (p-1)/3;	//s^2 + s
				int tt = 4*x + 1;
				int t = (int)Math.sqrt(tt);
				if (tt == t*t) c ++;
			}
		}
		System.out.println(c);
	}

}
